#include <iostream>
#include <vector>

/** leetcode #2680 最大或值
 * 关键解析:
 *  1.按位或运算的特性：只要一个元素在某一位为1，结果中该位就为1
 *  2.乘以2相当于二进制左移一位，低位补0
 * 
 * 最优策略:将所有的操作应用于同一个元素， 因为高位的一个1比低位的多个1贡献更大
 * 
 * 题解:
 *  选择哪个元素进行k次操作，可以使整个数组的或值最大
 *  对于每个元素nums[i]，我们考虑将k次操作都用在它身上，即这个元素变为 nums[i] << k。同时，其他元素（即除了nums[i]以外的所有元素）的或值是多少？这个或值我们可以通过预处理得到。
 */

namespace S1 {
    class Solution{
    public:
        long long maximumOr(std::vector<int>& nums, int k) {
            int n = nums.size();
            // 预处理前缀或和后缀或数组
            std::vector<long long> prefix(n + 1, 0), suffix(n + 1, 0);
            
            for (int i = 0; i < n; i ++) {
                prefix[i+1] = prefix[i] | static_cast<long long>(nums[i]);
            }

            for (int i = n -1; i >= 0; i --) {
                suffix[i] = suffix[i + 1] | static_cast<long long>(nums[i]);
            }

            long long best_candidate = 0;
            for (int i = 0; i < n; i ++) {
                long long rest_i = prefix[i] | suffix[i +1];     // 整个数组按位或的结果     题目要求:计算整个数组的或值 nums[0] | nums[1] | ... | nums[n-1]

                long long candidate = rest_i | (static_cast<long long>(nums[i]) << k);
                if (candidate > best_candidate) {
                    best_candidate = candidate;
                }
            }

            return best_candidate;
        }
    };
}